# 三个妖怪三个和尚过河，任意时候妖怪的数量都不能大于和尚，过河方式

# 自己分析：每次过河，去的时候转移2个，回来的时候转移1个或2个
# 0表示和尚，1表示妖怪，运送形式[0,0][0,1][1,1][1][0]
initial = {1: 3, 0: 3, 'boat':1}
destination = {1:0, 0:0, 'boat':0}
boat = [{1: 1, 0: 1}, {1: 2, 0: 0}, {1: 0, 0: 2}, {1: 1, 0: 0}, {1: 0, 0: 1}]
# 记录目的岸状态，如果有重复了则不执行， 临时记录每次的两岸状态[[{初始岸},{目的岸}],...]
record_dest = []
record_process = []
# record_init = []
# record_init_dest_temp = []
# 记录运送次数，奇数为去，偶数为回
i_num = 1


# 输送函数，接受两岸人员状态的字典，start为输送方，finish为接收方。
def transport(start, finish, i_num):
    record_init_dest_temp = []
    for boat_dict in boat:
        new_start = {}
        new_finish = {}
        new_start[0] = start[0] - boat_dict[0]
        new_finish[0] = finish[0] + boat_dict[0]
        new_start[1] = start[1] - boat_dict[1]
        new_finish[1] = finish[1] + boat_dict[1]
        new_start['boat'] = 0
        new_finish['boat'] = 1
        if new_start[0] < 0 or new_start[1] < 0 or ((new_finish[0] < new_finish[1]) and new_finish[0] != 0)or ((new_start[0] < new_start[1]) and new_start[0] != 0):
            continue
        if i_num % 2 == 0:
            if [new_finish, new_start] in record_process:
                continue
            # record_init.append(new_finish)
            record_dest.append(new_start)
            record_init_dest_temp.append([new_finish, new_start])
        else:
            if [new_start, new_finish] in record_process:
                continue
            # record_init.append(new_start)
            record_dest.append(new_finish)
            record_init_dest_temp.append([new_start, new_finish])
    return record_init_dest_temp


# 去目的岸 transport(initial, destination, 奇数)
# while finish is False:
def gogo(initial, destination, i_num):
    if i_num % 2 == 0:
        may_list = transport(destination, initial, i_num)
    else:
        may_list = transport(initial, destination, i_num)
    # print(may_list)
    i_num += 1
    for may_state in may_list:
        # print(may_state)
        if may_state[1] == {0: 3, 1: 3, 'boat': 1}:
            print(record_process)
            print('完成')
            return
        # transport(may_state[0], may_state[1], i_num)
        record_process.append(may_state)
        # print(may_state[0], may_state[1], i_num)
        gogo(may_state[0], may_state[1], i_num)
        record_process.remove(may_state)
    return

gogo(initial, destination, i_num)




# 小结：对于过河和返回两种转换，用了一个计数器来区分，从而通过一个函数，就实现了两种不同的状态转换
# 不要直接修改原状态，也不要用new状态=原状态。直接建立new状态，再给new赋值
# 建立一个列表记录经历的状态，循环中的递归调用后，要删除本次循环中新加入的状态再经历下一次循环
# （因为循环下的所有状态都是不同的可能性，一种方法中，只可以出现一种，不删就重复了）。
# 判断不重复的情况时，只跟当前情况下所经历过的状态比，不要建立一整个列表记录所有状态！！！（因为不同方法间可能会经历相同的状态）
# 书中说方法只有4种，但是本程序输出了10几种方法，不知道问题出在哪里
